package stackqueuelinkedlist;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class MaxQueue {
	MaxStack A = new MaxStack();
	MaxStack B = new MaxStack();
	
	public void enqueue(int n){
		B.push(n);
	}
	
	public int dequeue(){
		if(A.isEmpty()){
			while(!B.isEmpty()){
				A.push(B.pop());
			}
		}
		return A.pop();
	}
	
	public int max(){
		return Math.max(A.max(), B.max());
	}
	

	public static class MaxStack {
		public Stack<Integer> s = new Stack<Integer>();
		public Stack<Integer> max = new Stack<Integer>();

		public void push(int i) {
			s.push(i);
			// "=" needed to support duplicate
			if (max.isEmpty() || i >= max.peek()) {
				max.push(i);
			}
		}

		public int pop() {
			int i = s.pop();
			if (max.peek() == i) {
				max.pop();
			}
			return i;
		}

		public int max() {
			if(max.isEmpty())
				return -1;
			return max.peek();
		}
		
		public boolean isEmpty(){
			return s.isEmpty();
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MaxQueue mq = new MaxQueue();
		mq.enqueue(5);
		mq.enqueue(6);
		mq.enqueue(3);
		mq.enqueue(4);
		mq.enqueue(4);
		mq.enqueue(3);
		mq.dequeue();
		mq.dequeue();
		System.out.println(mq.max());
		mq.dequeue();
		mq.dequeue();
		System.out.println(mq.max());
		
	}

}
